#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using pii = pair < ll, ll >;
using vec = vector < int >;
using veg = vector < pii >;

ll read() {
    ll x = 0; bool f = 0; char ch = getchar(); while(!isdigit(ch)) f |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = x * 10 + (ch ^ 48),ch = getchar(); return f ? -x : x;
}

const int N = 1e5 + 10;

int n,id[N];
ll val[N],eans[N];
ll cur = 2,tot = 0,ans = 0;
priority_queue < pii , vector < pii >, greater < pii > > q;

int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    n = in;
	rep(i, 1, n) id[i] = i,val[i] = in;
	sort(id + 1,id + n + 1,[](int a,int b) { return val[a] < val[b]; });
	rep(i, 1, n) {
		int x = id[i]; ll t = val[x];
		if(t <= 1) { eans[x] = 9; continue; }
		while(t > tot) {
			ll nxt = cur;
			if(q.size() && q.top().fi <= nxt && t - tot >= q.top().fi) {
				ans++; pii v = q.top(); tot += q.top().fi; q.pop();
				v.fi *= v.se; q.push(v);
			} else {
				if(t - tot < nxt) {
					break;
				} else {
					ans++; tot += nxt; q.push({nxt * nxt - nxt,nxt}); cur++;
				}
			}
		}
		eans[id[i]] = ans;
	}
	rep(i, 1, n) printf("%lld\n",eans[i]);
	return 0;
}
